#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣1685. 有序数组中差绝对值之和
// 【难度】中等
// 【提交】2025.10.09 https://leetcode.cn/problems/sum-of-absolute-differences-in-a-sorted-array/submissions/669113629/
// 【标签】前缀和；数组；数学
class Solution_LC1685 {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 0);
        vector<int> pfs(n + 1, 0);
        for (int i = 0; i < n; i++) {
            pfs[i + 1] = pfs[i] + nums[i];
        }
        for (int i = 0; i < n; i++) {
            int ls = nums[i] * i - pfs[i];
            int rs = (pfs[n] - pfs[i + 1]) - nums[i] * (n - i - 1);
            res[i] = ls + rs;
        }
        return res;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个非递减有序整数数组nums，对于每个nums[i]，计算所有元素与nums[i]的绝对差之和。
 * 即result[i] = sum(|nums[i] - nums[j]|) 其中0 <= j < nums.length且j != i。
 * 模型：前缀和+数学推导，利用数组有序性简化计算。
 * 
 * 二、标准解法状态设计
 * 1. 计算前缀和数组pfs，其中pfs[i]表示前i个元素的和。
 * 2. 对于每个位置i，将差绝对值之和分为左侧和右侧两部分：
 *    - 左侧：所有小于nums[i]的元素与nums[i]的差值和
 *    - 右侧：所有大于nums[i]的元素与nums[i]的差值和
 * 3. 利用前缀和数组和数学公式高效计算左右两侧的差值和。
 * 
 * 三、你的实现思路
 * 使用前缀和技巧，通过数学推导将差绝对值之和分解为左右两部分。
 * 利用数组有序性，将O(n²)的暴力解法优化为O(n)的高效解法。
 * 
 * 四、逐行注释（带细节提醒）
 * vector<int> res(n, 0); // 初始化结果数组
 * vector<int> pfs(n + 1, 0); // 初始化前缀和数组
 * 
 * for (int i = 0; i < n; i++) { // 计算前缀和
 *     pfs[i + 1] = pfs[i] + nums[i];
 * }
 * 
 * for (int i = 0; i < n; i++) { // 计算每个位置的差绝对值之和
 *     int ls = nums[i] * i - pfs[i]; // 左侧差值和
 *     int rs = (pfs[n] - pfs[i + 1]) - nums[i] * (n - i - 1); // 右侧差值和
 *     res[i] = ls + rs; // 总差值和
 * }
 * 
 * 五、正确性证明
 * 利用数组有序性和前缀和的性质：
 * 1. 左侧：对于所有j < i，有nums[j] <= nums[i]，所以|nums[i]-nums[j]| = nums[i]-nums[j]
 *    左侧差值和 = Σ(nums[i]-nums[j]) = nums[i]*i - Σnums[j] = nums[i]*i - pfs[i]
 * 2. 右侧：对于所有j > i，有nums[j] >= nums[i]，所以|nums[i]-nums[j]| = nums[j]-nums[i]
 *    右侧差值和 = Σ(nums[j]-nums[i]) = Σnums[j] - nums[i]*(n-i-1) = (pfs[n]-pfs[i+1]) - nums[i]*(n-i-1)
 * 3. 总差值和 = 左侧 + 右侧
 * 
 * 六、复杂度
 * 时间：O(n)，需要两次遍历数组。
 * 空间：O(n)，需要前缀和数组存储中间结果。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 时间复杂度低，将O(n²)优化为O(n)；
 *   - 利用数学推导和前缀和，算法高效；
 *   - 代码简洁，实现优雅。
 * 缺点：
 *   - 需要额外的O(n)空间存储前缀和；
 *   - 数学推导需要一定的思维能力。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (nums.empty()) return {};
 * 2. 可以使用单个变量累积前缀和，进一步优化空间复杂度到O(1)；
 * 3. 对于教学场景，可以添加注释解释数学推导过程。
 * 
 * 九、一句话总结
 * 通过前缀和和数学推导，你的实现高效地解决了有序数组中差绝对值之和的问题，
 * 展现了利用数学优化算法效率的能力。
 */